#include <stdio.h>
#include <limits.h>

// 存储两个最小值和两个最大值的结构体
typedef struct {
    int min1;  // 最小
    int min2;  // 第二小
    int max2;  // 第二大
    int max1;  // 最大
} TwoMinMax;

// 对小规模数组（≤4个元素）直接求结果
TwoMinMax solveSmall(int arr[], int left, int right) {
    TwoMinMax res;
    int len = right - left + 1;
    int temp[4];  // 临时存储子数组元素
    for (int i = 0; i < len; i++) {
        temp[i] = arr[left + i];
    }
    // 排序（升序）
    for (int i = 0; i < len; i++) {
        for (int j = i + 1; j < len; j++) {
            if (temp[i] > temp[j]) {
                int t = temp[i];
                temp[i] = temp[j];
                temp[j] = t;
            }
        }
    }
    // 根据长度赋值
    if (len == 1) {
        res.min1 = res.min2 = res.max2 = res.max1 = temp[0];
    } else if (len == 2) {
        res.min1 = temp[0];
        res.min2 = temp[0];  // 确保min1 < min2，这里特殊处理
        res.max2 = temp[1];
        res.max1 = temp[1];
    } else if (len == 3) {
        res.min1 = temp[0];
        res.min2 = temp[1];
        res.max2 = temp[1];
        res.max1 = temp[2];
    } else {  // len == 4
        res.min1 = temp[0];
        res.min2 = temp[1];
        res.max2 = temp[2];
        res.max1 = temp[3];
    }
    return res;
}

// 合并两个子问题的结果
TwoMinMax merge(TwoMinMax left, TwoMinMax right) {
    TwoMinMax res;
    // 求两个最小值：从四个候选（left.min1, left.min2, right.min1, right.min2）中选前两位
    int mins[4] = {left.min1, left.min2, right.min1, right.min2};
    for (int i = 0; i < 4; i++) {
        for (int j = i + 1; j < 4; j++) {
            if (mins[i] > mins[j]) {
                int t = mins[i];
                mins[i] = mins[j];
                mins[j] = t;
            }
        }
    }
    res.min1 = mins[0];
    res.min2 = mins[1];
    
    // 求两个最大值：从四个候选（left.max1, left.max2, right.max1, right.max2）中选后两位
    int maxs[4] = {left.max1, left.max2, right.max1, right.max2};
    for (int i = 0; i < 4; i++) {
        for (int j = i + 1; j < 4; j++) {
            if (maxs[i] < maxs[j]) {
                int t = maxs[i];
                maxs[i] = maxs[j];
                maxs[j] = t;
            }
        }
    }
    res.max1 = maxs[0];
    res.max2 = maxs[1];
    
    return res;
}

// 递归求两个最大和两个最小值
TwoMinMax findTwoMinMax(int arr[], int left, int right) {
    int len = right - left + 1;
    if (len <= 4) {
        return solveSmall(arr, left, right);
    }
    int mid = (left + right) / 2;
    TwoMinMax leftRes = findTwoMinMax(arr, left, mid);
    TwoMinMax rightRes = findTwoMinMax(arr, mid + 1, right);
    return merge(leftRes, rightRes);
}

int main() {
    int n;
    printf("请输入数组长度n: ");
    scanf("%d", &n);
    int arr[n];
    printf("请输入%d个整数: ", n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    
    TwoMinMax res = findTwoMinMax(arr, 0, n - 1);
    printf("两个最小值: %d, %d\n", res.min1, res.min2);
    printf("两个最大值: %d, %d\n", res.max2, res.max1);  // 按min1<min2<max2<max1顺序
    return 0;
}